\subsection{Calssificazione: l'algoritmo K-means}\label{sec:impl_kmeans}
Il clustering in uno spazio Euclideo N-dimensionale $\Re^N$, consiste nel dividere un dato insieme di $n$ punti,
in un numero $\mathcal{K}$ di gruppi, aventi una caratteristica metrica in comune. A seconda della metrica scelta i pattern verranno di conseguenza assegnati ad un determinato cluster. 
Preso un insieme di $n$ punti $\mathcal{S}=\{\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_n\}$ e $\mathcal{K}$ cluster, 
rappresentati da $C_1,C_2,\dots,C_k$ devono sussistere le seguenti condizioni:
\begin{equation}\label{eq:condizio}
\begin{array}{l}
     C_i \neq \emptyset  \quad \mbox{per} \quad i=1,\dots,K\\
     C_i \cap C_j = \emptyset \quad \mbox{per} \quad i=1,\dots,K \quad \mbox{e} \quad i\neq j\\
     \bigcup_{i=1}^k C_i = \mathcal{S}
\end{array}
\end{equation}
Il K-means è un algoritmo iterativo di ricerca in salita ``hill climbing''. Esso può essere diviso essenzialmente in tre punti principali:
\begin{enumerate}
 \item Scelta iniziale dei $K$ centri dei cluster $\mathbf{z}_1,\mathbf{z}_2,\dots, \mathbf{z}_k$ presi 
  casualmente all'interno dei n punti $\{\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_n\}$.
 \item Assegnare i punti $\mathbf{x}_i, \quad i = 1,2,\dots, n$ ai cluster $C_j, \quad j=1,2,\dots,K$, se:
\begin{equation}\label{eq:appar}
|| \mathbf{x}_i - \mathbf{z}_j|| \leq || \mathbf{x}_i - \mathbf{z}_p||, \quad p = 1,2,\dots, K \quad \mbox{e} \quad j \neq p
\end{equation}
\item Calcolare i nuovi centri dei cluster, avvicinando ogni centro verso il baricentro del gruppo pattern a lui associati, ovvero:
\begin{equation}\label{eq:moveK}
\mathbf{z}_i^* = \frac{1}{n_i} \sum_{x_j \in C_i} \mathbf{x}_j \quad i = 1,2,\dots, K
\end{equation}
dove $n_i$ è il numero di elementi appartenenti al cluster $C_i$
%\item continuare il procedimento ripartendo dal punto 2) fin tanto che non vi sono più variazioni della posizione dei centri $\mathbf{z}_i$.
\end{enumerate}

L'implementazione dell'algoritmo descritto è stata divisa in due metodi, entrambi definiti nella classe \textbf{Population}.
Il primo metodo, \texttt{metricDivision}, si occupa di calcolare tutte le distanze di tutti i centri da tutti i punti, utilizzando 
la metrica Euclidea:% N-dimensionale definita dalla formula: 
$$d(\mathbf{x}, \mathbf{y}) = \|\mathbf{x} - \mathbf{y}\| = \sqrt{\sum_{i=1}^n (x_i - y_i)^2}.$$
Calcolate tutte le distanze, ogni punto viene associato al centroide più vicino ad esso, e conservando tale associazione nell'istanza \textit{p2c} della classe \textbf{Chromosome}. 
Il metodo \texttt{clusterize} si occupa invece della modifica della posizione dei centri secondo la formula~\ref{eq:moveK}. Durante questa fase, vengono contati gli elementi 
appartenenti a ciascun centroide. Nel caso in cui un centroide non rispetti la prima delle condizioni~\ref{eq:condizio}, è stata prevista una piccola variazione casuale 
della sua posizione in modo tale da permettere ad esso di tornare a contribuire attivamente alla classificazione, nell'iter successivo.  